/*
实验5-1 树的同构
分数 25
作者 陈越
单位 浙江大学

给定两棵树  T1​ 和 T2​。如果 T1​ 可以通过若干次左右孩子互换就变成 T2​，则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的，因为我们把其中一棵树的结点A、B、G的左右孩子互换后，就得到另外一棵树。而图2就不是同构的。
fig1.jpg
图1
图2

现给定两棵树，请你判断它们是否是同构的。
输入格式:

输入给出2棵二叉树的信息。对于每棵树，首先在一行中给出一个非负整数 n (≤10)，即该树的结点数（此时假设结点从 0 到 n−1 编号）；随后 n 行，第 i 行对应编号第 i 个结点，给出该结点中存储的 1 个英文大写字母、其左孩子结点的编号、右孩子结点的编号。如果孩子结点为空，则在相应位置上给出 “-”。给出的数据间用一个空格分隔。注意：题目保证每个结点中存储的字母是不同的。
输出格式:

如果两棵树是同构的，输出“Yes”，否则输出“No”。
输入样例1（对应图1）：

8
A 1 2
B 3 4
C 5 -
D - -
E 6 -
G 7 -
F - -
H - -
8
G - 4
B 7 6
F - -
A 5 1
H - -
C 0 -
D - -
E 2 -

输出样例1:

Yes

输入样例2（对应图2）：

8
B 5 7
F - -
A 0 3
C 6 -
H - -
D - -
G 4 -
E 1 -
8
D 6 -
B 5 -
E - -
H - -
C 0 2
G - 3
F - -
A 1 4

输出样例2:

No
*/

/*
03-树1 树的同构
*/
#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 10
#define ElementType char

typedef struct TreeNode *PtrTreeNode;
typedef struct TreeNode TreeNode;
struct TreeNode {
    ElementType data;
    PtrTreeNode left;
    PtrTreeNode right;
};

PtrTreeNode read(PtrTreeNode nodes) {
    int n;
    scanf("%d\n", &n);
    // 有父节点
    int *haveParent = (int*)calloc(n, sizeof(int));
    for (int i=0; i<n; i++) {
        char lidx, ridx;
        scanf("%c %c %c\n", &nodes[i].data, &lidx, &ridx);
        // printf("%c %c %c\n", nodes[i].data, lidx, ridx);
        if (lidx == '-') {
            nodes[i].left = NULL;
        } else {
            nodes[i].left = &nodes[lidx-'0'];
            haveParent[lidx-'0'] = 1;
        }
        if (ridx == '-') {
            nodes[i].right = NULL;
        } else {
            nodes[i].right = &nodes[ridx-'0'];
            haveParent[ridx-'0'] = 1;
        }
    }
    PtrTreeNode root = NULL;
    for (int i=0 ;i<n; i++) {
        if (!haveParent[i]) {
            root = &nodes[i];
            break;
        }
    }
    free(haveParent);
    return root;
}

void PreorderTraversal(PtrTreeNode root) {
    if (root == NULL) {
        return;
    }
    printf("%c ", root->data);
    PreorderTraversal(root->left);
    PreorderTraversal(root->right);
}

int Isomorphic(PtrTreeNode t1, PtrTreeNode t2) {
    if (t1 == NULL && t2 == NULL) {
        // 都NULL，相同
        return 1;
    }
    if ((t1 == NULL && t2 != NULL) || (t1 != NULL && t2 == NULL)) {
        // 有一个NULL,不同
        return 0;
    }
    if (t1->data != t2->data) {
        // 元素不相等,不同
        return 0;
    }
    if (t1->left == NULL && t2->left == NULL) {
        // 左节点都NULL, 比较右边
        return Isomorphic(t1->right, t2->right);
    }
    if (t1->left != NULL && t2->left != NULL && t1->left->data == t2->left->data) {
        // 左节点都不NULL, 并且元素相同，不交换比较
        return Isomorphic(t1->left, t2->left) && Isomorphic(t1->right, t2->right);
    } else {
        // 交换比较左右节点
        return Isomorphic(t1->left, t2->right) && Isomorphic(t1->right, t2->left);
    }
}

int main() {
    // 预先分配t1, t2的内存空间
    TreeNode t1nodes[MAX_SIZE], t2nodes[MAX_SIZE];
    PtrTreeNode t1 = read(t1nodes);
    PtrTreeNode t2 = read(t2nodes);
    // PreorderTraversal(t1);
    // printf("\n");
    // PreorderTraversal(t2);
    // printf("\n");

    if (Isomorphic(t1, t2)) {
        printf("Yes\n");
    } else {
        printf("No\n");
    }
    return 0;
}
